package String.easy;

import java.util.*;

/**
 * 1. 问题描述
 *      给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi]
 *      表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
 *      题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。
 *
 * 2. 算法分析
 *      1. 使用暴力穷举的方式
 *          假设有n条路线，每次我们从中选择一条路线，之后从剩下的路线中在选择一条路线，依次下去
 *          此算法的时间复杂度以指数级别，不推荐
 *
 *      2. leetcode上的大神提供的思路：利用集合差求解(厉害!!!!!,这个思路简单，效率高)
 *          实际上由于题目中已经表明不存在循环路线。并且保证至少有一条路线，那么我们简化
 *          一下上述的模型，假设我们的路线模型为 [[A,B],[C,D],[B,C],[D,E]]，则我们有
 *          一下路线：A-->B-->C-->D-->E,其中总的城市为A，B，C，D，E，起始城市为A，B
 *          C，D，则两者只差就是最终的目的地E
 *
 *          即：我们通过一次遍历将paths分成两个部分一部分是起点城市，一部分是总的城市，这两个集合的
 *          差值就是我们的目的地
 *
 *          思考一下这个方式是如何想出来的?
 *             省略(暂时还没有想到)
 *
 *      3. 采用hashmap实现上述问题的求解
 *
 * 3. 代码实现
 *
 */
@SuppressWarnings("all")
public class 旅行终点站 {
    public static void main(String[] args) {
        List<String> path1 = new ArrayList<>(); path1.add("London"); path1.add("New York");
        List<String> path2 = new ArrayList<>(); path2.add("New York"); path2.add("Lima");
        List<String> path3 = new ArrayList<>(); path3.add("Lima"); path3.add("Sao Paulo");
        List<List<String>> paths = new ArrayList<>(); paths.add(path1); paths.add(path2); paths.add(path3);
        System.out.println(destCity2(paths));
    }

    /**
     * 采用集合差解决上述问题
     * @param paths
     * @return
     */
    public static String destCity(List<List<String>> paths) {
        if(paths.size() == 1) {return paths.get(0).get(1);}
        Set<String> citys = new HashSet<>(); // 存放所有城市
        Set<String> starts = new HashSet<>(); // 存放所有的起点城市
        for(List<String> path : paths) {
            // 由于集合是不重复的，所以set会自动帮助我们取出重复的城市
            citys.add(path.get(0)); citys.add(path.get(1));
            starts.add(path.get(0));
        }
        //  求citys集合和starts集合的差集
        String destCity = null;
        for(String city : citys) {
            if(!starts.contains(city)) {
                destCity = city;
                break;
            }
        }
        return destCity;
    }

    /**
     * 采用hashmap实现
     * 第一次遍历paths，我们将paths中的每个path的起点作为key，终点作为value
     * 第二次，我们以第一条路线为开始，如果第一条路线的key在hashmap中，取出，当前key的value
     * 将其作为新的key，判断此时更新之后的key是否在hashmap中如果在重复上述步骤，实际上我们知道只有目的地
     * 是无法作为key的，因为不能作为下一个城市的起点，所以当key不在其中时，就是我们最终想要的结果
     * @param paths
     * @return
     */
    public static String destCity2(List<List<String>> paths) {
        Map<String,String> map = new HashMap<>();
        for(List<String> path:paths) {
            map.put(path.get(0),path.get(1));
        }
        String key = paths.get(0).get(0);
        while(map.containsKey(key)) {
            key = map.get(key);
        }
        return key;
    }
}
